package day_2022_7_to_8.day48;

import java.util.Stack;

/**
 * @author haomin
 * @date 2022/07/29 21:37
 **/
public class Day14_1_Num921_MinAddToMakeValid {
    // 方法一：栈方法
    class Solution {
        public int minAddToMakeValid(String s) {
            Stack<Character> stack = new Stack<>();
            if(s.length() == 0) return 0;
            int i = 0;
            int count = 0;
            stack.push(s.charAt(i));
            while (i < s.length()-1){
                i++;
                char a = stack.peek();
                char b = s.charAt(i);
                if(a == '(' && b == ')'){
                    stack.pop();
                    i++;
                    if(i < s.length() && stack.isEmpty()){
                        stack.push(s.charAt(i));
                    }else if(i < s.length() && !stack.isEmpty()){
                        i--;
                        continue;
                    }else if(i >= s.length()) break;
                }else if(a == '(' && b == '('){
                    stack.push(b);
                }else if(a == ')'){
                    stack.pop();
                    count++;
                    stack.push(b);
                }
            }
            count = count + stack.size();
            return count;
        }
    }

    // 方法二：找规律
    // 出现一个'('个数+1；
    // 若已出现'('，再出现一个右')'个数-1，否则个数加+1
    class Solution2 {
        public int minAddToMakeValid(String s) {
            int left = 0, right = 0;
            for(char a : s.toCharArray()){
                if(a == '(') left++;
                else {
                    if(left == 0) right++;
                    else left--;
                }
            }
            return left + right;
        }
    }
}